7、砝码称重
题目 砝码称重
思路分析
状态表示 从前i个砝码里面选 选到总重量恰好为j的所有选法的数量（只需要看有没有 count可以转变成bool)
状态计算 不选的话 就是f[i-1][j]的状态 选的话 有两种可能 如果在左边 就是加上这个砝码后重量才达到j 所以状态应该是从f[i-1][j-w[i]]转移而来 如果加在右边 那就是减去这个砝码（加上这个负砝码）后才达到j重量 所以状态从f[i-1][j+w[i]]转移而来
再考虑初始化 0个砝码里选出重量为0合法 1~n个砝码中选出重量0 好像也合法 因为可以什么都不选 那就全初始化成1
最后的答案就是 遍历f[n][1-M] 看有多少个不为0
另外一个点就是 左边6 右边2量出来的4 和 左边2 右边6量出来的-4是一样的 都是4这个重量 所以可以加绝对值
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=2e5+10;
int f[N][M]; //1-M个物品中选(最多100个物品) 体积恰好为1-M(M最大为1e5 因为有两边 所以开双倍)
int w[N];//每个物品的价值
int n,m;
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>w[i];
m+=w[i];//能称出的最大重量肯定是所有之和
}
for(int i=0;i<=n;i++)
f[i][0]=1;//什么都不选也是一种选法
for(int i=1;i<=n;i++){//枚举砝码
for(int j=0;j<=m;j++){//枚举重量
f[i][j]=f[i-1][j]+f[i-1][abs(j-w[i])]+f[i-1][j+w[i]];
}
}
int ans=0;
for(int i=1;i<=m;i++)
if(f[n][i])
ans++;
cout<<ans;
return 0;
}
💬 评论